package com.huangpeng.algorithm.dataStructure;

/**
 * @Author huangpeng
 * @Title Trie 树
 * @Package
 * @Date 2021/7/22 16:42
 * @Description
 * @Version 1.0
 */
public class Trie {
    /**
     *
     */
    public class TrieNode{
        public char data;
        public TrieNode[] children = new TrieNode[26];
        public boolean isEndingChar = false;
        public TrieNode(char data){
            this.data = data;
        }
    }
    private TrieNode root = new TrieNode('/');// 存储无意义字符

    /**
     * 往 Trie 树中插入一个字符串
     * @param text
     */
    public void insert(char[] text){
        TrieNode p = root;
        int length = text.length;
        for (int i = 0; i < length; i++) {
            int index = text[i] - 'a';
            if(p.children[index] == null){
                TrieNode newTrieNode = new TrieNode(text[i]);
                p.children[index] = newTrieNode;
            }
            p = p.children[index];
        }
        p.isEndingChar = true;
    }

    /**
     * 在 Trie 树中查找一个字符串
     * @param pattern
     * @return
     */
    public boolean find(char[] pattern){
        TrieNode p = root;
        int length = pattern.length;
        for (int i = 0; i < length; i++) {
            int index = pattern[i] - 'a';
            if(p.children[index] == null){
                return false;// 不存在 pattern
            }
            p = p.children[index];
        }
        if(!p.isEndingChar){// 不能完全匹配，只是前缀
            return false;
        }else{// 找到 pattern
            return true;
        }
    }
}
